ECE 6605 - Information Theory

Prof. Matthieu Bloch

Thursday, October 26, 2023

Announcements

  • Assignment 2 and Midterm
    • Grading almost finished
    • Bonus assignment to boost midterm due Thursday October 26, 2023
    • Watch office hour video
  • Assignment 3
    • Posted later today
  • Last time
    • Converse of channel coding theorem
  • Today
    • Achievability of channel coding theorem
    • Soft-covering

Midterm feedback - things to pay attention to

Where are channels coming from?

Channel coding

Image
Channel coding model
  • Unless otherwise specified, we assume for now that the message is uniformly distributed

A \((n,M_n)\) code \(\calC\) for channel coding over a discrete memoryless source \(P_{Y|X}\) consists of an encoding function \(f_n:\{1,\cdots,M_n\}\to\calX^n\) and a decoding function \(g_n:\calY^n\to\{1,\cdots,M_n\}\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)
    2. The average probability of decoding error \[ P_e^{(n)}\eqdef \P{\widehat{M}\neq M} \eqdef \sum_{m=1}^{M_n}\frac{1}{M_n}\sum_{y^n}P_{Y|X}(y^n|f_n(m))\indic{g_n(y^n)\neq m} \]

Channel capacity

  • Define again \[ C\eqdef \sup\left\{R: \exists \set{(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\geq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0\right\} \]

For a discrete memoryless channel characterized by \(P_{Y|X}\), \(C = \max_{P_X}\mathbb{I}(X;Y)\)

  • Remarks
    • This result is called the channel coding theorem
    • Given a statistical characterization of a channel, there is a limit to how fast we can sent data
  • Proof of the result
    • We will use again an achievability and a converse
    • We will first develop some intuition about codes

Achievability (random coding)

  • Consider a generic channel \((\calU,P_{V|U},\calV)\) with message set \(\{1,\cdots,M\}\)

  • For \(\gamma>0\), let

    \[\begin{align*} \calA_\gamma \eqdef \left\{(u,v)\in\calU\times\calV:\log\frac{P_{V|U}(v|u)}{P_V(v)}\geq\gamma\right\} \end{align*}\]

  • Encoder

    • For each \({m}\in\{1,\cdots,M\}\), \(f(m)\) is a codeword \(u\) drawn independently according to \(P_U\).

  • Decoder: \(g\) is defined as follows. Upon receiving a channel ouptut \(v\):

    • If there exists a unique \(\hat{m}\) such that \((f(\hat{m}),v)\in\calA_\gamma\), return \(m^*\);
    • Else, return a pre-defined arbitrary \(m_0\)

For any \(\gamma>0\),

\[\begin{align*} \E[C]{P_e(C)} \leq \P[P_UP_{V|U}]{(U,V)\notin \calA_\gamma} + M2^{-\gamma}. \end{align*}\]

Soft covering

Image
Soft covering coding model
  • We assume for now that the message is uniformly distributed and that the input reference distirbution \(P_X\) is known and fixed.

A \((n,M_n)\) code \(\calC\) for soft covering over a discrete memoryless source \(P_{Z|X}\) consists of an encoding function \(f_n:\{1,\cdots,M_n\}\to\calX^n\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)
    2. The approximation of the output statistics \[ S^{(n)}\eqdef \mathbb{V}(P_Z^n,P_Z^{\otimes n}) \]

Channel resolvability

  • Define \[ C_{\textsf{r}}\eqdef \inf\left\{R: \exists \set{(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}D^{(n)}=0\right\} \]

For a discrete memoryless channel characterized by \(P_{Z|X}\) and an input \(P_X\), \(C_{\textsf{r}} = \mathbb{I}(X;Z)\)

  • Remarks
    • This result is called the channel coding theorem
    • Given a statistical characterization of a channel and an input distribution, we can randomize to lose structure
  • Proof of the result
    • We will use again an achievability and a converse

Achievability (random coding)

  • Consider a generic channel \((\calU,P_{V|U},\calV)\) with message set \(\{1,\cdots,M\}\)

  • For \(\gamma>0\), let

    \[\begin{align*} \calC_\gamma \eqdef \left\{(u,v)\in\calU\times\calV:\log\frac{P_{V|U}(v|u)}{P_V(v)}\leq\gamma\right\} \end{align*}\]

  • Encoder

    • For each \({m}\in\{1,\cdots,M\}\), \(f(m)\) is a codeword \(u\) drawn independently according to \(P_U\).

For any \(\gamma>0\),

\[\begin{align*} \E[C]{S(C)} \leq \P[P_UP_{V|U}]{(U,V)\notin \calC_\gamma} + \frac{1}{2}\sqrt{\frac{2^{\gamma}}{M}}. \end{align*}\]